Labeling outerplanar graphs with maximum degree three

Abstract

An L(2, 1)-labeling of a graph G is an assignment of a non-negative integer to each vertex of G such that adjacent vertices receive integers that differ by at least two and vertices at distance two receive distinct integers. The span of such a labeling is the difference between the largest and smallest integers used. The λ-number of G, denoted by λ(G), is the minimum span over all L(2, 1)-labelings of G. Bodlaender et al. conjectured that if G is an outerplanar graph of maximum degree Δ, then λ(G) ≤ Δ + 2. Calamoneri and Petreschi proved that this conjecture is true when Δ ≥ 8 but false when Δ = 3. Meanwhile, they proved that λ(G) ≤ Δ + 5 for any outerplanar graph G with Δ = 3 and asked whet..